/**
 * 
 */
package backtrack.passed;

import java.util.ArrayList;

/**
 * @author xyyi
 *
 */
public class NQueens {
	/**
	The n-queens puzzle is the problem of placing n queens on an n�n chessboard such that no two queens attack each other.



	Given an integer n, return all distinct solutions to the n-queens puzzle.

	Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

	For example,
	There exist two distinct solutions to the 4-queens puzzle:

	[
	 [".Q..",  // Solution 1
	  "...Q",
	  "Q...",
	  "..Q."],

	 ["..Q.",  // Solution 2
	  "Q...",
	  "...Q",
	  ".Q.."]
	]
	 */
	public ArrayList<String[]> solveNQueens(int n) {
		ArrayList<String[]> result = new ArrayList<String[]>();
		if (n < 1)
			return result;

		char[][] board = new char[n][n];
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				board[i][j] = '.';
			}
		}
		int[] rows = new int[n];

		solveNQueens(rows, 0, board, result);
		return result;
	}

	private void solveNQueens(int[] rows, int row, char[][] board,
			ArrayList<String[]> result) {
		if (row == board.length) {
			String[] strs = new String[board.length];
			for (int i = 0; i < strs.length; i++) {
				strs[i] = String.valueOf(board[i]);
			}
			result.add(strs);
		} else {
			for (int col = 0; col < board[0].length; col++) {
				if (!isConfilict(rows, row, col)) {
					rows[row] = col;
					board[row][col] = 'Q';
					solveNQueens(rows, row + 1, board, result);
					board[row][col] = '.';
				}

			}
		}
	}

	private boolean isConfilict(int[] rows, int row, int col) {
		for (int i = 0; i < row; i++) {
			if (rows[i] == col || Math.abs(i - row) == Math.abs(rows[i] - col)) {
				return true;
			}
		}

		return false;
	}

	/**
	N-Queens II
	
	Follow up for N-Queens problem.

	Now, instead outputting board configurations, return the total number of distinct solutions.
	 */
	public int totalNQueens(int n) {
		if (n < 1)
			return 0;
		int[] rows = new int[n];

		return totalNQueens(rows, 0);
	}

	private int totalNQueens(int[] rows, int row) {
		if (row == rows.length) {
			return 1;
		} else {
			int total = 0;
			for (int col = 0; col < rows.length; col++) {
				if (!isConfilict(rows, row, col)) {
					rows[row] = col;
					total += totalNQueens(rows, row + 1);
				}
			}

			return total;
		}
	}

	/**
	 * 
	 */
	public NQueens() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
